package com.study.线段树;

public class SegmenTree {
	// 原序列的信息从0开始，但在arr中是从1开始的
	// sum[]模拟线段树维护区间和
	// lazy[]为懒增加标记
	// change[]为更新的值
	// update[]为懒更新的标记
	private int MAXN;
	private int[] arr;
	private int[] sum;
	private int[] lazy;
	private int[] change;
	private boolean[] update;

	public SegmenTree(int[] origin) {
		MAXN = origin.length + 1;// arr从1开始，所以需要多一个长度
		arr = new int[MAXN];// arr[0]不用，从1开始使用
		for (int i = 1; i < MAXN; i++) {
			arr[i] = origin[i - 1];
		}
		// 以下的辅助数组均开辟 4倍 的空间
		sum = new int[MAXN << 2];// 用来支持脑补概念中，某一个范围的累加和
		lazy = new int[MAXN << 2];// 用来支持脑补概念中，某一个范围没有往下传的累加信息
		change = new int[MAXN << 2];// 用来支持脑补概念中，某一个范围更新的值
		update = new boolean[MAXN << 2];// 用来支持脑补概念中，某一个范围是否有更新操作
		build(1, origin.length, 1);
	}

	// 在初始化阶段，先把sum数组，填好
	// 在arr[l~r]范围上，去build，1~N
	// rt:这个范围对应在sum中的下标
	private void build(int l, int r, int rt) {
		if (l == r) {
			sum[rt] = arr[l];// 说明这个我们脑补二叉树中的最底层，那么就是原数组的值
			return;
		}
		// 如果l != r
		int mid = (l + r) >> 1;// 求出范围的中心
		build(l, mid, rt << 1);// build左范围
		build(mid + 1, r, rt << 1 | 1);// build右范围,rt << 1相当于整除2，整体与运算一个1，就相当于加1
		// 左右范围build好之后
		pushUp(rt);// 更新sum中rt位置的值
	}

	// 更新sum中rt位置的值，由它的左右两个范围的值相加
	private void pushUp(int rt) {
		sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
	}

	// 下发懒任务（包括懒增加、懒更新），懒更新比懒增加先下发
	// ln表示左孩子的节点个数，rn为右孩子的节点个数
	private void pushDown(int rt, int ln, int rn) {
		// 懒更新比懒增加先下发，因为懒更新在操作上会覆盖懒增加，
		// 如果下发时，既有懒增加，又有懒更新，那么时间上，
		// 这时候的懒增加一定是发生在懒更新后的，所以下发时，懒更新需要先下发

		// 如果rt位置有懒更新任务
		if (update[rt]) {
			// 左右孩子得到懒更新标记
			update[rt << 1] = true;
			update[rt << 1 | 1] = true;
			// 左右孩子更新change
			change[rt << 1] = change[rt];// 懒更新是覆盖
			change[rt << 1 | 1] = change[rt];
			// 左右孩子的懒增加全部清空，被懒更新覆盖
			lazy[rt << 1] = 0;
			lazy[rt << 1 | 1] = 0;
			// 左右孩子更新sum
			sum[rt << 1] = ln * change[rt];
			sum[rt << 1 | 1] = rn * change[rt];
			// 任务下发完成，父节点的懒更新标记取消
			update[rt] = false;
		}
		// 如果rt位置有懒增加任务
		if (lazy[rt] != 0) {
			// 左右孩子得到懒增加任务
			lazy[rt << 1] += lazy[rt];// 懒增加是叠加
			lazy[rt << 1 | 1] += lazy[rt];
			// 左右孩子更新sum
			sum[rt << 1] += lazy[rt] * ln;
			sum[rt << 1 | 1] += lazy[rt] * rn;
			// 清楚rt位置的懒增加标记
			lazy[rt] = 0;
		}
	}

	// L..R -> 任务范围（目标范围），所有的值累加C
	// l..r -> 当前的范围
	// l..r -> 范围对应在sum的rt位置
	public void add(int L, int R, int C, int l, int r, int rt) {
		// 如果目标范围把当前的范围给覆盖了，那么直接更新当前范围的sum
		if (L <= l && r <= R) {
			sum[rt] += C * (r - l + 1);// 这个范围有(r - l + 1)个节点，每个节点都增加C
			lazy[rt] += C;// 蓝增加标记
			return;
		}
		// 任务 L，R 没有把l..r的范围覆盖
		// 要把任务下发
		int mid = (l + r) >> 1;// 求出l..r的中心
		// 把当前的任务下发之前，要把之前的懒任务先下发（包括懒增加、懒更新）
		pushDown(rt, mid - l + 1, r - mid);
		// 左右孩子又被覆盖到一点范围，就需要接受任务
		if (L <= mid) {
			add(L, R, C, l, mid, rt << 1);
		}
		if (mid < R) {
			add(L, R, C, mid + 1, r, rt << 1 | 1);
		}
		// 左右孩子的任务下发完毕，更新当前位置的sum
		pushUp(rt);
	}

	// 更新任务的操作与add相似，需要注意的是，更新操作是覆盖，覆盖懒增加，覆盖sum，而懒增加是累加。
	public void update(int L, int R, int C, int l, int r, int rt) {
		// 如果目标范围把当前的范围给覆盖了，那么直接更新当前范围的sum
		if (L <= l && r <= R) {
			sum[rt] = C * (r - l + 1);// 这里是直接覆盖
			update[rt] = true; // 标记懒更新标记
			change[rt] = C;// 更新的值
			lazy[rt] = 0; // 覆盖懒增加
			return;
		}
		int mid = (l + r) >> 1;
		// 下发当前的懒更新任务之前，要把之前的懒任务先下发（包括懒增加、懒更新）
		pushDown(rt, mid - l + 1, r - mid);
		// 左右孩子只要有被目标范围覆盖到一点点，就要接收懒任务
		if (L <= mid) {
			update(L, R, C, l, mid, rt << 1);
		}
		if (mid < R) {
			update(L, R, C, mid + 1, r, rt << 1 | 1);
		}
		// 左右孩子的sum更新完毕，更新rt位置的sum
		pushUp(rt);
	}

	// 查询，步骤几乎跟add一样
	public long query(int L, int R, int l, int r, int rt) {
		if (L <= l && r <= R) {
			return sum[rt];
		}
		int mid = (l + r) >> 1;
		pushDown(rt, mid - l + 1, r - mid);
		long ans = 0;
		if (L <= mid) {
			ans += query(L, R, l, mid, rt << 1);
		}
		if (mid < R) {
			ans += query(L, R, mid + 1, r, rt << 1 | 1);
		}
		return ans;
	}

	// 编写正确的操作类，普通的操作
	public static class Right {
		private int[] arr;

		public Right(int[] origin) {
			arr = new int[origin.length + 1];
			for (int i = 1; i <= origin.length; i++) {
				arr[i] = origin[i - 1];
			}
		}

		public void add(int L, int R, int C) {
			for (int i = L; i <= R; i++) {
				arr[i] += C;
			}
		}

		public void update(int L, int R, int C) {
			for (int i = L; i <= R; i++) {
				arr[i] = C;
			}
		}

		public long query(int L, int R) {
			long ans = 0;
			for (int i = L; i <= R; i++) {
				ans += arr[i];
			}
			return ans;
		}
	}

	// 返回一个长度不超过len，元素最大值不超过max的数组
	public static int[] generateRandomArray(int len, int max) {
		int size = (int) (Math.random() * len) + 1;
		int[] origin = new int[size];
		for (int i = 0; i < size; i++) {
			origin[i] = (int) (Math.random() * max) - (int) (Math.random() * max);// 保证了有正数和负数，等概率
		}
		return origin;
	}

	public static boolean test() {
		int len = 100;
		int max = 100;
		int testTimes = 5000;
		int addOrUpdateTimes = 1000;
		int queryTimes = 500;
		for (int i = 0; i < testTimes; i++) {
			int[] origin = generateRandomArray(len, max);
			SegmenTree seg = new SegmenTree(origin);
			int l = 1;
			int r = origin.length;
			int rt = 1;
			Right rig = new Right(origin);
			for (int j = 0; j < addOrUpdateTimes; j++) {
				int num1 = (int) (Math.random() * origin.length) + 1;
				int num2 = (int) (Math.random() * origin.length) + 1;
				int L = Math.min(num1, num2);
				int R = Math.max(num1, num2);
				int C = (int) (Math.random() * max) - (int) (Math.random() * max);// 有正数和负数
				// 一般的概率增加，一般的概率更新
				if (Math.random() < 0.5) {
					seg.add(L, R, C, l, r, rt);
					rig.add(L, R, C);
				} else {
					seg.update(L, R, 1, l, r, rt);
					rig.update(L, R, 1);
				}
			}
			for (int j = 0; j < queryTimes; j++) {
				int num1 = (int) (Math.random() * origin.length) + 1;
				int num2 = (int) (Math.random() * origin.length) + 1;
				int L = Math.min(num1, num2);
				int R = Math.max(num1, num2);
				long ansSeg = seg.query(L, R, l, r, rt);
				long ansRig = rig.query(L, R);
				if (ansSeg != ansRig) {
					return false;
				}
			}
		}
		return true;
	}
}
